package hard;

import java.util.Arrays;

/**
 * Created by daodao on 2017/12/1.
 * Problem 4
 * Description: There are two sorted arrays nums1 and nums2 of size m and n respectively.
 * Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
 *
 * Example 1: nums1 = [1, 3]
 *            nums2 = [2]
 *            The median is 2.0
 * Example 2: nums1 = [1, 2]
 *            nums2 = [3, 4]
 *            The median is (2 + 3)/2 = 2.5
 */
public class MedianOfTwoSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double ave = 0;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int mid = (len1 + len2) / 2;
        boolean isEven = (len1 + len2) % 2 == 0;
        int[] nums = new int[len1 + len2];
        int i, j, k;
        for (i = 0, j = 0, k = 0; i < len1 && j < len2; k++) {
            if (nums1[i] < nums2[j]) {
                nums[k] = nums1[i];
                i++;
            } else {
                nums[k] = nums2[j];
                j++;
            }
        }
        while (i < len1) {
            nums[k++] = nums1[i++];
        }
        while (j < len2) {
            nums[k++] = nums2[j++];
        }

        if (isEven) {
            ave = (nums[mid - 1] + nums[mid]) / 2.0;
        } else {
            ave = nums[mid];
        }
        return ave;
    }
}
